//递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。 
//
// 示例 1： 
//
// 
// 输入：A = 1, B = 10
// 输出：10
// 
//
// 示例 2： 
//
// 
// 输入：A = 3, B = 4
// 输出：12
// 
//
// 提示： 
//
// 
// 保证乘法范围不会溢出 
// 
//
// Related Topics 位运算 递归 数学 👍 121 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-17 00:10:38
 * @description 面试题 08.05.递归乘法
 */
public class RecursiveMulitplyLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 RecursiveMulitplyLcci fun=new RecursiveMulitplyLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int multiply(int A, int B) {
        if(B==1) return A;
		return A + multiply(A, B - 1);
    }
	public int multiply1(int A, int B) {
		int min = Math.min(A, B);
		int max = Math.max(A, B);
		int ans = 0;

		for (int i = 0; min != 0; i++) {
			if ((min & 1) == 1) {
				ans += max << i;
			}
			min >>= 1;
		}

		return ans;
	}
	int re = 0;
	public int multiply2(int A, int B) {
		int min = A,max=B;
		if(A>B){
			min = B;
			max = A;
		}
		core(min,max,0);
		return re;
	}
	public void core(int min,int max,int i){
		if((min>>>i)==0) return;
		if(((min>>>i)&1)==1){
			re+=max<<i;
		}
		core(min,max,i+1);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
